home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
CD Exchange
/
CD Exchange - Volume 1.iso
/
d.t.p
/
utils
/
others
/
pcal
/
exprpars.c
< prev
next >
Wrap
C/C++ Source or Header
|
1992-02-21
|
9KB
|
374 lines
/*
* exprpars.c - Pcal routines concerned with parsing if{n}def expressions
*
* Contents:
*
* do_xxx
* lookup_token
* next_token
* parse_expr
*
* Revision history:
*
* 4.0 AWR 02/06/91 Author
*
*/
/*
* Standard headers:
*/
#include <ctype.h>
#include <string.h>
#include <stdio.h>
/*
* Pcal-specific definitions:
*/
#include "pcaldefs.h"
#include "pcalglob.h"
/*
* Macros:
*/
/*
* token type code definitions:
*/
#define TK_UNKNOWN 0 /* codes returned by next_token() */
#define TK_IDENT 1
#define TK_LPAREN 2
#define TK_RPAREN 3
#define TK_UNARYOP 4
#define TK_BINARYOP 5
#define TK_ENDINPUT 6
#define TK_STARTINPUT 7 /* special code for start symbol */
/* bit position for token type codes (cf. where_ok[] below) */
#define ID_OK (1 << TK_IDENT)
#define LP_OK (1 << TK_LPAREN)
#define RP_OK (1 << TK_RPAREN)
#define UO_OK (1 << TK_UNARYOP)
#define BO_OK (1 << TK_BINARYOP)
#define ST_OK (1 << TK_STARTINPUT)
#define NEVER_OK 0
/* is token "curr" legal after "prev"? (cf. where_ok[] below) */
#define IS_LEGAL(curr, prev) (where_ok[curr] & (1 << (prev)))
/*
* operator-related definitions:
*/
#define OP_AND 0 /* operator subcodes */
#define OP_OR 1
#define OP_XOR 2
#define OP_NEGATE 3
#define ENDINPUT_PREC -1 /* arbitrary number < lowest op. prec */
#define OR_PREC 1 /* operator precedence levels */
#define XOR_PREC 2
#define AND_PREC 3
#define NEGATE_PREC 4
#define PAREN_PREC 8 /* arbitrary number > highest op. prec */
/* lower bits of operator stack entry are code; higher are precedence */
#define OPR_BITS 4
#define OPR_MASK ((1 << OPR_BITS) - 1)
#define PREC(op) ((op) >> OPR_BITS)
#define OPCODE(op) ((op) & OPR_MASK)
#define MAKE_OPR(p, o) (((p) << OPR_BITS) | (o))
#define MAX_OP 20 /* size of operand and operator stacks */
/*
* Globals:
*/
typedef short OPERAND; /* types for operand and operator stacks */
typedef short OPERATOR;
typedef struct {
char *name; /* token spelling */
short type; /* token type code */
short value; /* associated value */
} TOKEN;
/* token table - note that substrings must follow longer strings */
TOKEN token_tbl[] = {
"&&", TK_BINARYOP, OP_AND, /* synonym for "&" */
"&", TK_BINARYOP, OP_AND,
"||", TK_BINARYOP, OP_OR, /* synonym for "|" */
"|", TK_BINARYOP, OP_OR,
"!", TK_UNARYOP, OP_NEGATE,
"^", TK_BINARYOP, OP_XOR,
"(", TK_LPAREN, 0,
")", TK_RPAREN, 0,
NULL, TK_UNKNOWN, 0 /* must be last entry */
};
typedef struct {
short prec; /* precedence */
short type; /* token type (TK_UNARYOP or TK_BINARYOP) */
#ifdef PROTOS
OPERAND (*pfcn)(OPERAND *); /* dispatch function */
#else
OPERAND (*pfcn)(); /* dispatch function */
#endif
} OPR;
/* operator table - entries must be in same order as OP_XXX */
#ifdef PROTOS
static OPERAND do_and(OPERAND *);
static OPERAND do_or(OPERAND *);
static OPERAND do_xor(OPERAND *);
static OPERAND do_negate(OPERAND *);
#else
static OPERAND do_and(), do_or(), do_xor(), do_negate(); /* dispatch fcns */
#endif
OPR opr_tbl[] = {
AND_PREC, TK_BINARYOP, do_and, /* OP_AND */
OR_PREC, TK_BINARYOP, do_or, /* OP_OR */
XOR_PREC, TK_BINARYOP, do_xor, /* OP_XOR */
NEGATE_PREC, TK_UNARYOP, do_negate /* OP_NEGATE */
};
/* set of tokens which each token may legally follow (in TK_XXX order) */
int where_ok[] = {
NEVER_OK , /* TK_UNKNOWN */
ST_OK | LP_OK | UO_OK | BO_OK , /* TK_IDENT */
ST_OK | LP_OK | UO_OK | BO_OK , /* TK_LPAREN */
ID_OK | LP_OK | RP_OK , /* TK_RPAREN */
ST_OK | LP_OK | BO_OK , /* TK_UNARYOP */
ID_OK | RP_OK , /* TK_BINARYOP */
ST_OK | ID_OK | RP_OK /* TK_ENDINPUT */
};
/*
* do_xxx - dispatch functions for operators
*/
#ifdef PROTOS
static OPERAND do_and(OPERAND *ptop)
#else
static OPERAND do_and(ptop)
OPERAND *ptop;
#endif
{
return ptop[0] & ptop[-1];
}
#ifdef PROTOS
static OPERAND do_or(OPERAND *ptop)
#else
static OPERAND do_or(ptop)
OPERAND *ptop;
#endif
{
return ptop[0] | ptop[-1];
}
#ifdef PROTOS
static OPERAND do_xor(OPERAND *ptop)
#else
static OPERAND do_xor(ptop)
OPERAND *ptop;
#endif
{
return ptop[0] ^ ptop[-1];
}
#ifdef PROTOS
static OPERAND do_negate(OPERAND *ptop)
#else
static OPERAND do_negate(ptop)
OPERAND *ptop;
#endif
{
return ! ptop[0];
}
/*
* lookup_token - look up token in table; return pointer to table entry
*/
#ifdef PROTOS
static TOKEN *lookup_token(char *p)
#else
static TOKEN *lookup_token(p)
char *p;
#endif
{
TOKEN *ptok;
for (ptok = token_tbl;
ptok->name && strncmp(p, ptok->name, strlen(ptok->name));
ptok++)
;
return ptok;
}
/*
* next_token - fetch next token from input string; fill in its type and value
* and return pointer to following character
*/
#ifdef PROTOS
static char *next_token(char *p,
int *ptype,
int *pvalue)
#else
static char *next_token(p, ptype, pvalue)
char *p;
int *ptype;
int *pvalue;
#endif
{
TOKEN *ptok;
char tokbuf[STRSIZ], *pb;
#define NT_RETURN(p, t, v) \
if (1) { *ptype = t; *pvalue = v; return p; } else
while (*p && isspace(*p)) /* skip whitespace */
p++;
if (*p == '\0') /* end of input? */
NT_RETURN(p, TK_ENDINPUT, 0);
if (isalpha(*p) || *p == '-') { /* identifier or flag? */
pb = tokbuf; /* make local copy and look up */
while (*p && (isalpha(*p) || isdigit(*p) || *p == '_' ||
(pb == tokbuf && *p == '-')))
*pb++ = *p++;
*pb = '\0';
NT_RETURN(p, TK_IDENT, find_sym(tokbuf));
}
ptok = lookup_token(p); /* other token */
NT_RETURN(p + (ptok->name ? strlen(ptok->name) : 1), ptok->type,
ptok->value);
}
/*
* parse_expr - parses expression consisting of identifiers and logical
* operators; return TRUE if expression is true (identifier defined => true);
* FALSE if false; EXPR_ERR if syntax error in expression
*/
#ifdef PROTOS
int parse_expr(char *pbuf)
#else
int parse_expr(pbuf)
char *pbuf;
#endif
{
OPERAND opd_stack[MAX_OP]; /* operand stack - TRUE/FALSE values */
OPERATOR opr_stack[MAX_OP]; /* operator stack - precedence | op */
int value, token, plevel, prec, result, npop, opr, opd, prev_token, op;
plevel = 0; /* paren nesting level */
opd = opr = -1; /* indices of stack tops */
prev_token = TK_STARTINPUT; /* to detect null expressions */
if (DEBUG(DEBUG_PP))
FPR(stderr, "evaluating expression '%s'\n", pbuf);
do {
pbuf = next_token(pbuf, &token, &value);
/* check that the current token may follow the previous one */
if (! IS_LEGAL(token, prev_token))
return EXPR_ERR;
switch(token) {
case TK_IDENT: /* identifier => 1 if def, 0 if not */
opd_stack[++opd] = value != PP_SYM_UNDEF;
break;
case TK_LPAREN: /* left paren - bump nesting level */
++plevel;
break;
case TK_RPAREN: /* right paren - decrement nesting */
if (--plevel < 0)
return EXPR_ERR;
break;
case TK_ENDINPUT: /* end-of-input - treat as operator */
if (prev_token == TK_STARTINPUT)
return FALSE; /* null expr => FALSE */
/* fall through */
case TK_UNARYOP:
case TK_BINARYOP:
/* get precedence of operator, adjusting for paren
* nesting (TK_ENDINPUT has the lowest precedence
* of all, to unwind operand/operator stacks at end)
*/
prec = token == TK_ENDINPUT ? ENDINPUT_PREC :
(plevel * PAREN_PREC) + opr_tbl[value].prec;
/* pop (and perform) any equal- or higher-precedence
* operators on operator stack: extract operator,
* check for operand stack underflow, execute
* operator, adjust operand stack height and place
* result of operator on top
*/
for ( ;
opr >= 0 && PREC(opr_stack[opr]) >= prec;
opr--) {
op = OPCODE(opr_stack[opr]);
npop = opr_tbl[op].type == TK_UNARYOP ? 0 : 1;
if (opd < npop)
return EXPR_ERR;
result = (*opr_tbl[op].pfcn)(opd_stack + opd);
opd_stack[opd -= npop] = result;
}
/* push operator (if any) onto stack */
if (token != TK_ENDINPUT)
opr_stack[++opr] = MAKE_OPR(prec, value);
break;
default: /* should never get here */
return EXPR_ERR;
break;
}
prev_token = token;
}